package com.peng.leetcode.graph;

import java.util.*;

/**
 * FindItinerary
 *
 * @author: lupeng6
 * @create: 2021/1/8 11:34
 */
public class FindItinerary {

    public static void main(String[] args) {
        List<List<String>> tickets = new ArrayList<>();
//        tickets.add(Arrays.asList(new String[]{"MUC", "LHR"}));
//        tickets.add(Arrays.asList(new String[]{"JFK", "MUC"}));
//        tickets.add(Arrays.asList(new String[]{"SFO", "SJC"}));
//        tickets.add(Arrays.asList(new String[]{"LHR", "SFO"}));

        tickets.add(Arrays.asList(new String[]{"JFK","SFO"}));
        tickets.add(Arrays.asList(new String[]{"JFK","ATL"}));
        tickets.add(Arrays.asList(new String[]{"SFO","ATL"}));
        tickets.add(Arrays.asList(new String[]{"ATL","JFK"}));
        tickets.add(Arrays.asList(new String[]{"ATL","SFO"}));

        List<String> itinerary = new FindItinerary().findItinerary(tickets);
        System.out.println(itinerary);
    }

    private Map<String, PriorityQueue<String>> adjacency;

    private List<String> itinerary = new ArrayList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> adjacency = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            adjacency.putIfAbsent(from, new PriorityQueue<>());
            adjacency.get(from).offer(to);
        }
        this.adjacency = adjacency;
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }


    private void dfs(String from) {
        PriorityQueue<String> queue = adjacency.get(from);
        while (queue != null && !queue.isEmpty()) {
            String next = queue.poll();
            dfs(next);
        }
        itinerary.add(from);
    }

}
